package leetcode.linked;

import java.util.HashMap;

/**
 * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 * 示例 1：
 * <p>
 * 输入：head = [1,2,3,4,5], n = 2
 * 输出：[1,2,3,5]
 * <p>
 * 示例 2：
 * <p>
 * 输入：head = [1], n = 1
 * 输出：[]
 * <p>
 * 示例 3：
 * <p>
 * 输入：head = [1,2], n = 1
 * 输出：[1]
 * 提示：
 * <p>
 * 链表中结点的数目为 sz
 * 1 <= sz <= 30
 * 0 <= Node.val <= 100
 * 1 <= n <= sz
 * 进阶：你能尝试使用一趟扫描实现吗？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */


public class Solution19 {
    static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        public void print(ListNode node) {
            while (node != null) {
                System.out.println(node.val);
                node = node.next;
            }
        }
    }

    /**
     * 采用记录方式, 遍历一边就记录住元素,以及他的位置
     *
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode cur = head;
        HashMap<Integer, ListNode> nodeMap = new HashMap<>();
        int index = 0;
        while (cur != null) {
            nodeMap.put(index++, cur);
            cur = cur.next;
        }
        if (n > index) {
            return null;
        }
        if (n == index) {
            return head.next;
        }
        ListNode remNode = nodeMap.get(index - n);
        ListNode pre = nodeMap.get(index - n - 1);
        pre.next = remNode.next;
        remNode.next = null;
        return head;
    }

    public static void main(String[] args) {
        Solution19 solution19 = new Solution19();
        // 1->2->3->4->5->null
        ListNode listNode = solution19.removeNthFromEnd(new ListNode(1, new ListNode(2, new ListNode(3,
                new ListNode(4, new ListNode(5, null))))), 3);
        listNode.print(listNode);

    }
}
